package com.leetcode.根据算法进行分类.滑动窗口相关;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeSet;

/**
 * @author: xiaomi
 * @date: 2021/2/27
 * @description: 395. 至少有 K 个重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
 */
public class B_395_至少有K个重复字符的最长子串 {

    public static void main(String[] args) {
        B_395_至少有K个重复字符的最长子串 action = new B_395_至少有K个重复字符的最长子串();
//        test1(action);
        test2(action);
    }

    public static void test1(B_395_至少有K个重复字符的最长子串 action) {
        //3
        String s = "aaabb";
        int k = 3;
        int res = action.longestSubstring(s, k);
        System.out.println("res = " + res);
    }

    public static void test2(B_395_至少有K个重复字符的最长子串 action) {
        //3
        String s = "ababbc";
        int k = 2;
        int res = action.longestSubstring(s, k);
        System.out.println("res = " + res);
    }

    /**
     * 子串 = 子数组
     *
     * @param s
     * @param k
     * @return
     */
    public int longestSubstringFail(String s, int k) {
        if (s == null) {
            return 0;
        }
        int len = s.length();
        if (len == 0 || len < k) {
            return len;
        }
        char[] chars = s.toCharArray();
        //a-z:097-122
        int[] recordArr = new int[123];
        //记录种类数量 及 合法的种类数量 及 记录的最长子串的长度
        int kindNum = 0, legalNum = 0, res = 0;
        //character - 不满足时的索引
        HashMap<Character, List<Integer>> map = new HashMap<>();
        char cur;
        for (int i = 0; i < len; i++) {
            cur = chars[i];
            if (recordArr[cur] == 0) {
                kindNum++;
            }
            recordArr[cur]++;
            if (recordArr[cur] == k) {
                //只有本次接触到临界时，才需要修改 legalNum 的值
                legalNum++;
            }
        }
        //完成一次遍历后开始对不合格的字符处进行切割

        return 1;
    }


    /**
     * 定义一个全局的最长子串的长度，方便过滤重复计算
     */
    int maxLen = 0;
    int k = 0;

    /**
     * 测试用例给的数据不方便找到规律
     * --
     * 1.遍历完整的一遍后，如果发现中间存在不合格的字符，就将其切割
     * 2.计算切割后符合条件的长度
     *
     * @param s
     * @param k
     * @return
     */
    public int longestSubstring(String s, int k) {
        if (s == null) {
            return 0;
        }
        int len = s.length();
        if (len == 0 || len < k) {
            return 0;
        }
        this.k = k;
        char[] chars = s.toCharArray();
        getMaxLen(chars, 0, len);
        return maxLen;
    }

    /**
     * @param chars
     * @param begin [
     * @param end   )
     */
    private int getMaxLen(char[] chars, int begin, int end) {
        int len = end - begin;
        if (len < maxLen) {
            //如果本次递归长度已经小于 之前的出来的结果，那就可以跳过
            return 0;
        }

        //a-z:097-122
        int[] recordArr = new int[123];
        List<Integer>[] recordList = new ArrayList[123];

        char cur;
        for (int i = begin; i < end; i++) {
            cur = chars[i];
            if (recordArr[cur] == 0) {
                recordList[cur] = new ArrayList<>();
            }
            recordArr[cur]++;
            recordList[cur].add(i);
        }
        //再次遍历 recordArr 找到不满足的地方，进行截取并计算
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 97; i < 123; i++) {
            if (recordArr[i] < k && recordArr[i] > 0) {
                List<Integer> list = recordList[i];
                for (int j = list.size() - 1; j >= 0; j--) {
                    treeSet.add(list.get(j));
                }
            }
        }
        if (treeSet.isEmpty()){
            maxLen = Math.max(maxLen, len);
            return len;
        }
        int lastBegin = begin;
        int res = 0;
        for (Integer i :
                treeSet) {
            res = Math.max(res, getMaxLen(chars, lastBegin, i));
            lastBegin = i + 1;
        }
        res = Math.max(res, getMaxLen(chars, lastBegin, end));
        maxLen = Math.max(maxLen, res);
        return res;
    }

}
